#include <iostream>
#include <cstdio>
using namespace std;
long long a,b,x,y,t;
void f(long long  a,long long b){if(b){f(b,a%b);t=x;x=y;y=t-(a/b)*y;}else{x=1; y=0;}}

int main()
{
    freopen("mod.in","r",stdin);
	freopen("mod.out","w",stdout);
	cin>>a>>b;f(a,b);x%=b;while(x<0)x+=b;cout<<x;
	fclose(stdin);
	fclose(stdout);
	return 0;
}

